""" 阶乘 和 排列的 关系

排列	阶乘进制表示	    计算方式
123	    000	        0×2! + 0×1! + 0×0! = 0
132	    010	        0×2! + 1×1! + 0×0! = 1
213	    100	        1×2! + 0×1! + 0×0! = 2
231	    110	        1×2! + 1×1! + 0×0! = 3
312	    200	        2×2! + 0×1! + 0×0! = 4
321	    210	        2×2! + 1×1! + 0×0! = 5

举例 n=3  k=4   n=3的组成阶乘为 2! 1！ 0！
k-=1  k=3  # 从0开始计数
k=3=1*2! + 1*1! + 0*0!  ==> 110 (阶乘进制表示)
nums=[1,2,3] # 用这三个数排列组合
110 表示 从nums中选第一个，去除，后再选第一个，后去除选第0个
得到 231
"""

class Solution:
    def getPermutation(self, n: int, k: int) -> str:

        # 预先 计算阶乘
        fact = [1] * n
        for i in range(1, n):
            fact[i] = fact[i - 1] * i

        nums = list(range(1, n + 1))  # 可选数字
        res = []
        k -= 1
        for i in range(n - 1, -1, -1):
            idx = k // fact[i]  # 当前位的阶乘进制数字
            res.append(str(nums.pop(idx)))  # 从剩余数字中选择
            k %= fact[i]  # 更新预算

        return "".join(res)
